package homework.exp03;

import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.Scanner;

public class B {
    static Scanner cin = null;

    static {
        try {
            cin = new Scanner(new FileReader(new File("B.in")));
        } catch (IOException e) {
            cin = new Scanner(System.in);
        }
    }

    public static void main(String[] args) {

        int t = cin.nextInt();
        while (t-- > 0) {
            int m = cin.nextInt();
            int n = cin.nextInt();
            int result = countWays(m, n);
            System.out.println(result);
        }
        cin.close();
    }

    private static int countWays(int m, int n) {
        if (m == 0 || n == 1) {
            return 1;
        }
        if (m < n) {
            return countWays(m, m);
        }
        return countWays(m, n - 1) + countWays(m - n, n);
    }
}